/*
题目: 将 x 减到 0 的最小操作数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
 */
public class MinOperations {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        // 原题: 每次去掉最左边或者最右边的元素
        // 使用滑动窗口计算 sum(中间元素) = sum(nums) - x 的最长子数组长度
        // 由于都是正的, curSum 只具有递增性
        long sum = 0L, curSum = 0L; // 数组总和 & 当前总和
        for (int num : nums)    sum += num;
        long tar = sum - x;


        int left = 0;
        int max = -1;  // 记录最长满足 tar 的长度
        for (int i = 0; i < n; i ++) {
            curSum += nums[i];
            while (left < n && curSum > tar) {
                curSum -= nums[left ++];
            }
            if (curSum == tar) {
                max = Math.max(i - left + 1, max);
            }
        }

        return max == -1 ? -1 : n - max;
    }
}
